package numSquares

import (
	"fmt"
	"math"
)

// leetcode 279 完全平方数

func work2(n int) int {
	dp := make([]int, n+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = math.MaxInt32
	}
	dp[0] = 0
	// 建立的dp的元素意思是整数值为n的完全平方数的最小数量
	k := minN(n)
	fmt.Println(k)
	for i := 0; i < k; i++ {
		for j := i * i; j <= n; j++ {
			fmt.Println(dp[j], dp[j-i*i]+1, dp, i, j)
			dp[j] = min(dp[j], dp[j-i*i]+1)
		}
	}
	fmt.Println(dp)
	return dp[n]
}

func minN(n int) int {
	cur := 0
	fmt.Println("cur", n)
	for i := 0; i <= n+1; i++ {
		if i*i > n {
			fmt.Println(i, n)
			cur = i
		}
	}
	return cur
}
